//! 简单的堆管理
//!

// ------------------------------------------------------------------------------------------
// 全局变量

use crate::link::{BlockLink, LIST};
use core::{
    ptr::{null, NonNull},
    sync::atomic::Ordering,
};
use std::alloc::Layout;

/// 堆的大小
pub(crate) const HEAP_SIZE: usize = 4 * (1 << 20); // 4 MB

/// 全局变量实现的堆
pub(crate) static mut HEAP: [u8; HEAP_SIZE] = [0; HEAP_SIZE];

/// BlockLink这个结构体位于每一个分配的内存的开始位置，必须要正确的内存对齐。
pub(crate) static HEAP_STRUCT_SIZE: usize = size_of::<BlockLink>();

/// 出去对齐之后，真实可用的空间
pub(crate) static mut HEAP_REAL_AVAILABEL_SIZE: usize = 0;

/// 剩余多少自由空间，用来跟踪
pub(crate) static mut FREE_BYTES_REMAINNING: usize = HEAP_SIZE;

pub(crate) static HEAP_MINIMUM_BLOCK_SIZE: usize = HEAP_STRUCT_SIZE * 4;
// ------------------------------------------------------------------------------------------

/// 申请内存
pub(crate) unsafe fn malloc(mut want_size: usize) -> *mut u8 {
    let mut ret = null::<u8>() as *mut u8;
    let mut layout =
        Layout::from_size_align_unchecked(want_size, align_of::<BlockLink>()).pad_to_align();

    while LIST.lock.compare_and_swap(false, true, Ordering::AcqRel) {
        continue;
    }

    // 检查初始化
    if LIST.end.is_null() {
        heap_init();
    }

    if layout.size() > 0 {
        layout =
            Layout::from_size_align_unchecked(layout.size() + HEAP_STRUCT_SIZE, layout.align());
    }

    if layout.size() > 0 && layout.size() < HEAP_REAL_AVAILABEL_SIZE {
        let mut prev_node = &mut LIST.first;
        let mut current_node = prev_node.next_free; // 第一个肯定有
        while (&*current_node).size < want_size && !(&*current_node).next_free.is_null() {
            prev_node = &mut *current_node;
            current_node = (&*current_node).next_free;
        }

        if current_node != LIST.end {
            // 找到了， 跳过BlockLink结构体
            ret = (prev_node.next_free as *mut u8).add(HEAP_STRUCT_SIZE) as *mut u8;

            // This block is being returned for use so must be taken out of
            // the list of free blocks.
            prev_node.next_free = (&*current_node).next_free;

            // if the block is larger than required it can be split into two.
            if (&*current_node).size - want_size > HEAP_MINIMUM_BLOCK_SIZE {
                // this block is to be split into two. Create a new block following the number of bytes requested.

                let new_block_link =
                    ((current_node as *mut u8).add(layout.size())) as *mut BlockLink;
                (&mut *new_block_link).size = (&*current_node).size - layout.size();
                (&mut *current_node).size = layout.size();

                // inset the new block into the list of free blocks.
                insert_block_into_free_list(new_block_link);
            }
            FREE_BYTES_REMAINNING -= layout.size();
        }
    }

    LIST.lock.store(false, Ordering::Release);
    ret
}

/// 释放
pub(crate) unsafe fn free(p: *mut u8) {
    while LIST.lock.compare_and_swap(false, true, Ordering::AcqRel) {
        continue;
    }

    let block_ptr = p.sub(HEAP_STRUCT_SIZE) as *const BlockLink;
    FREE_BYTES_REMAINNING += (&*block_ptr).size;
    insert_block_into_free_list(block_ptr as _);

    LIST.lock.store(false, Ordering::Release);
}

pub(crate) unsafe fn insert_block_into_free_list(mut block_insert: *mut BlockLink) {
    let start = &mut LIST.first;
    let mut iter = start;

    // Iterate through the list until a block is found that has a higher address
    // than the block being inserted.
    while iter.next_free < block_insert {
        iter = &mut *iter.next_free;
    }

    let puc = iter as *const BlockLink as *const u8;
    if puc.add(iter.size) == block_insert as *const u8 {
        iter.size += (&*block_insert).size;
        block_insert = iter as *const BlockLink as _;
    }

    let puc = block_insert as *const u8;

    if puc.add((&*block_insert).size) == iter.next_free as *const u8 {
        if iter.next_free != LIST.end {
            (&mut *block_insert).size += (&*iter.next_free).size;
            (&mut *block_insert).next_free = (&*iter.next_free).next_free;
        } else {
            (&mut *block_insert).next_free = LIST.end;
        }
    } else {
        (&mut *block_insert).next_free = iter.next_free;
    }

    if iter as *const BlockLink != block_insert {
        iter.next_free = block_insert;
    }
}

/// 堆初始化
#[inline(always)]
unsafe fn heap_init() {
    // 第一个节点并没有占用堆的空间，是一个全局变量，指示下一个节点的位置
    LIST.first.size = 0;
    LIST.first.next_free = as_ptr_mut_align(as_ptr_from_ref(&HEAP));

    // end节点，用于标记空闲块列表的结束并插入在堆空间的末尾。
    let end: *mut u8 = as_ptr_from_ref(&HEAP).add(HEAP_SIZE).sub(HEAP_STRUCT_SIZE);
    let align_end = align_down(end as _, align_of::<BlockLink>()) as *mut u8;
    LIST.end = align_end as *mut BlockLink;
    {
        let end = &mut *LIST.end;
        end.size = 0;
        end.next_free = null::<BlockLink>() as _;
    }

    // 真实可用的空间，是总的减去偏移的
    HEAP_REAL_AVAILABEL_SIZE = align_end.offset_from(as_ptr_from_ref(&HEAP)) as usize
        - ((LIST.first.next_free as usize) - (&HEAP[0] as *const u8 as usize));

    // 创键第一个自由节点, 这个节点在HEAP上
    let bl = &mut *LIST.first.next_free;
    bl.size = HEAP_REAL_AVAILABEL_SIZE;
    bl.next_free = LIST.end;
    FREE_BYTES_REMAINNING = HEAP_REAL_AVAILABEL_SIZE;
}

#[inline(always)]
fn as_ptr_mut_align<T>(ptr: *mut u8) -> *mut T {
    let align_value = align_of::<T>();
    if !ptr.is_aligned_to(align_value) {
        // 没有对齐
        return ((ptr as usize + align_value) & !(align_value - 1)) as *mut T;
    }
    ptr.cast()
}

// 向大的方向对齐
#[inline(always)]
fn align_up(ptr: *mut u8, align: usize) -> *mut () {
    ((ptr as usize + align) & !(align - 1)) as *mut ()
}

// 向小的方向对齐
#[inline(always)]
fn align_down(ptr: *mut (), align: usize) -> *mut () {
    ((ptr as usize) & !(align - 1)) as *mut ()
}

#[inline(always)]
fn as_ptr_from_ref(heap: &[u8]) -> *mut u8 {
    &heap[0] as *const u8 as *mut u8
}

// print the list of free
pub unsafe fn print_free_list() {
    if LIST.end.is_null() {
        heap_init();
    }

    let first = &LIST.first;
    let mut iter = first.next_free;
    println!("remainning_bytes: {}", FREE_BYTES_REMAINNING);
    let mut i = 1;
    while iter != LIST.end {
        println!("{}: size: {}, addrees: {:p}", i, (&*iter).size, iter);
        iter = (&*iter).next_free;
        i += 1;
    }
}
